package hot_100;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: Darven
 * @createTime: 2025-10-03  15:28
 * @description: TODO
 */
public class P23 {

    //    public ListNode mergeKLists(ListNode[] lists) {
//        // 循环合并链表
//        ListNode res=lists[0];
//
//        for(int i=1;i<lists.length;i++){
//            res=merge(res,lists[i]);
//        }
//
//        return res;
//    }
//
//    private ListNode merge(ListNode left, ListNode right) {
//        ListNode dummy=new ListNode(0);
//        ListNode cur=dummy;
//        while(left!=null&&right!=null){
//            if(left.val<right.val){
//                cur.next=left;
//                left=left.next;
//            }else{
//                cur.next=right;
//                right=right.next;
//            }
//            cur=cur.next;
//        }
//        cur.next=left==null?right:left;
//        return dummy.next;
//    }
    class Status implements Comparable<Status> {
        int val;
        ListNode h;

        public Status(int val, ListNode h) {
            this.val = val;
            this.h = h;
        }

        @Override
        public int compareTo(Status o) {
            return this.val-o.val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        PriorityQueue<Status> list = new PriorityQueue<>();
        // 通过优先队列存放，然后根据最小值拿出来，拼接到ans列表里面
        for (ListNode node : lists) {
            if(node!=null){
                list.add(new Status(node.val, node));
            }
        }

        ListNode ans = new ListNode(0);
        ListNode cur = ans;

        while (!list.isEmpty()) {
            Status poll = list.poll();
            ListNode h = poll.h;
            cur.next = h;
            h = h.next;
            if (h != null) list.add(new Status(h.val, h));
            cur = cur.next;
        }

        return ans.next;
    }
}
